package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

//用时0 100%，内存2.2MB 5%
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	var s []*ListNode
	initListNode := head
	s = append(s, head)
	for head.Next != nil {
		head = head.Next
		s = append(s, head)
	}
	if len(s) == 1 {
		return nil
	} else if len(s) == n {
		return s[1]
	}
	if n == 1 {
		s[len(s)-2].Next = nil
	} else {
		s[len(s)-n-1].Next = s[len(s)-n+1]
	}
	return initListNode
}

//用时0 100%,内存2.1MB 59%
func removeNthFromEnd1(head *ListNode, n int) *ListNode {
	initListNode := head
	count := 1
	for head.Next != nil {
		head = head.Next
		count++
	}
	if count == 1 {
		return nil
	} else if count == n {
		return initListNode.Next
	}
	head = initListNode
	for count-1 > n {
		head = head.Next
		count--
	}
	head.Next = head.Next.Next
	return initListNode
}

//用双指针可以只遍历一次且内存消耗更少，两个指针间隔n，第一个指针指向哑节点{0,head}

func main() {
	ListNode1 := ListNode{11, nil}
	ListNode := ListNode{10, &ListNode1}
	fmt.Println(removeNthFromEnd1(&ListNode, 1))
	fmt.Println(removeNthFromEnd(&ListNode, 1))
}
